A potential target for improved immunotherapy of some adenocarcinomas is the tumor associated antigen, CEA. A direct immunogic approach to CEA-bearing tumor has been developed at the NCI using inoculation with a recombinant vaccinia virus that expresses the human CEA gene. Specific aims of this Phase I study are to determine tolerance/side effects of repeated vaccination with rV-CEA followed by repeated CEA peptide injection, to determine optimal biologic dose for CEA peptide injection and to assess any evidence of anti-tumor activity.